package com.fengye.algorithms.leecode.dp;

/**
 * @Author fengye
 * @Date 2023/5/17 6:06
 **/
public class DeleteAndEarn740 {
    public int deleteAndEarn(int[] nums) {

        int max = 0;
        // 先获取数组中最大的数
        for(int n : nums) {
            max = Math.max(max, n);
        }
        // 对数组中相同的数进行求和，就变的和打家劫舍一样的问题了
        int[] sum = new int[max+ 1];
        for(int n : nums) {
            sum[n] += n;
        }

        int[] dp = new int[sum.length];
        dp[0] = sum[0];
        dp[1] = Math.max(sum[0], sum[1]);
        for (int i = 2; i < sum.length; i++) {
            // 打i-2和i 与打i-1比
            dp[i] = Math.max(dp[i - 2] + sum[i], dp[i - 1]);
        }
        return dp[sum.length - 1];
    }


}
